class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int dest=-1,cur=0;cur<nums.size();++cur)
        {
            if(nums[cur] != 0)
            {
                swap(nums[++dest],nums[cur]);
            }
        }
        // int dest = -1,cur = 0;
        // while(cur<nums.size())
        // {
        //     if(nums[cur] != 0)
        //     {
        //         dest++;
        //         std::swap(nums[dest],nums[cur]);  
        //     }
        //     cur++;
        // }
    }
};
class Solution 
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        // 1、先找到最后一个复写的数
        int cur = 0,dest=-1;
        while(cur < arr.size())
        {
            if(arr[cur] == 0)
                dest+=2;
            else
                dest++;
            if(dest >= arr.size() - 1) // 此时表明cur就是我们要复写的数了
                break;
            cur++;
        }
        // 2、处理边界情况（cur下标数据0，可能导致dest++到数组外面）
        if(arr[cur]==0 && dest == arr.size())
        {
            arr[arr.size() - 1] = 0;
            cur -= 1;
            dest -= 2;
        }
        // 3、从后向前完成复写操作
        while(cur >= 0)
        {
            if(arr[cur] == 0)
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
            else
            {
                arr[dest--] = arr[cur--];
            }
        }
    }
};
class Solution 
{
public:
    int bitSum(int n) // 返回数字n的每一位数的平方和
    {
        int num,sum=0;
        while(n)
        {
            num = n%10;
            sum += num * num;
            n/=10;
        }
        return sum;
    }
    bool isHappy(int n) // 快慢指针，环里面两个位置的值相等为1就是快乐数，相等不为1就不是快乐数。（一定有环，鸽巢原理）
    {
        int slow = n;
        int fast = bitSum(n);
        while(slow != fast)
        {
            fast = bitSum(fast);
            fast = bitSum(fast);
            slow = bitSum(slow);
            
        }
        if(fast == slow && fast == 1)
        {
            return true;
        }
        return false;
    }
};
class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0,right = height.size()-1;
        int maxNum = INT_MIN;
        // left和right谁小谁就向中间走，计算出容积之后进行max保留最大容积
        while(left <= right)
        {
            maxNum = max(maxNum,(right-left) * min(height[left],height[right]));
            if(height[left] > height[right])
            {
                --right;
            }
            else
            {
                ++left;
            }
        }
        return maxNum;
    }
};
class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        // 判断3个数是否是三角形判断一次的方法 ： a <= b <= c && a+b>c  ---> 这样abc就构成一个三角形
        // 1、优化，进行快排
        sort(nums.begin(),nums.end());
        
        // 2、设置好第三条边的值，使用双指针，来确定第一条边和第二条边的值
        int ret = 0,n = nums.size();
        for(int i = n-1;i>=2;--i)
        {
            int left = 0,right = i-1;
            while(left < right)
            {
                // a是最小值，那么a无论是双指针范围中的什么值都是三角形，直接right-left记录所有个数。然后--right继续下一次范围判断
                if(nums[left] + nums[right] > nums[i])
                {
                    
                    ret += (right-left);
                    right--; 
                }
                // b是双指针范围最大值，b都不满足，那么其他值和a也就都不大于c了，直接++left进行下一个双指针范围的统计个数
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};